package com.tgy.algorithm.base.other;

import java.util.Arrays;

public class _KMP {

    public static int[] next(String pattern) {

        if (pattern == null || pattern.length() == 0) {
            return new int[0];
        }

        int len  = pattern.length();
        int[] result = new int[len];
        if (len == 0) {
            result[0] = -1;
        }

        if (len >= 2) {
            result[0] = -1;
            result[1] = 0;
        }

        char[] chars = pattern.toCharArray();
        int preIndex;
        for (int i = 2; i < len; i++) {
            preIndex = i - 1;
            while (true) {
                preIndex = result[preIndex];
                if (chars[preIndex] == chars[i - 1]) {
                    result[i] = preIndex + 1;
                    break;
                }else {
                    if (preIndex == 0) {
                        result[i] = 0;
                        break;
                    }
                }
            }
        }

        return result;
    }

    public static int[] next01(String pattern) {
        if (pattern == null || pattern.length() == 0) {
            return null;
        }

        int len = pattern.length();
        int[] res  = new int[pattern.length()];
        res[0] = -1;
        int index = 2;
        // preIndex 即代表index - 1位置的最大前缀长度，也代表要当前要比对的字符位置
        int preIndex  = 0;
        char[] chars = pattern.toCharArray();

        while (index < len) {
            if(chars[index - 1] == chars[preIndex]) {
                res[index++] =  1 + preIndex++;
            }else if (preIndex == 0) {
                res[index++] = 0;
            }else {
                preIndex = res[preIndex];
            }
        }
        return res;
    }

    public static void main(String[] args) {

        String pattern = "abaacabdaa";
        int[] result = next(pattern);
        int[] result01 = next01(pattern);
        System.out.println(Arrays.toString(result));
        System.out.println(Arrays.toString(result01));
    }
}
